class Solution {
public:
    // 建立一个包含K个元素的小堆
    void AdjustDown(vector<int>& nums, int index, int len) {
        int parent = index, child = parent * 2 + 1;
        while (child < len) {
            if (child + 1 < len && nums[child + 1] < nums[child]) child++;
            if (nums[child] < nums[parent]) {
                swap(nums[child], nums[parent]);
                parent = child;
                child = parent * 2 + 1;
            } else break;
        }
    }

    void BuildHead(vector<int>& nums, int k) {
        for (int i = k / 2 - 1; i >= 0; i--) {
            AdjustDown(nums, i, k);
        }
    }

    int findKthLargest(vector<int>& nums, int k) {
        BuildHead(nums, k);
        for (int i = k; i < nums.size(); i++) {
            if (nums[i] < nums[0]) continue;

            swap(nums[i], nums[0]);
            AdjustDown(nums, 0, k);
        }
        return nums[0];
    }
};
